package com.zhj.tree.redblack;

/**
 * 手写红黑树：
 * 1. 根节点的颜色是黑色
 * 2. 节点颜色要么是黑色、要么是红色
 * 3. 如何一个节点的颜色是红色，则它的节点必须是黑色，即不能有2个连续的红色节点
 * 4. 每个叶子节点都是黑色（这里的叶子节点都是为空的叶子节点）
 * 5. 从节点到该节点的叶子节点的所有路径上都包含相同数量的黑色节点
 *
 * 对红黑树的插入删除操作可以看作普通的二叉树完成操作，然后通过旋转（左旋、右旋）以及颜色调整来使得操作后的树满足红黑树的所有特性即可
 */
public class RedBlackTree {

    /** 根节点 */
    private RedBlackTreeNode root;


    public RedBlackTreeNode insert(int data) {
        RedBlackTreeNode insertNode = new RedBlackTreeNode(data);
        if (this.root == null) {
            this.root = insertNode;
            setBlack(insertNode);
        } else {
            RedBlackTreeNode parent = null;
            //根节点不为空
            RedBlackTreeNode node = root;

            //一直循环到 node 最后为空的节点，通过parent保存最后一个节点
            while (node != null) {
                parent = node;
                //如果根节点的数据大于插入的数据
                if (node.getData() >= data) {
                    //获取到左子树
                    node = node.getLeft();
                } else {
                    //右边子树
                    node = node.getRight();
                }
            }
            //parent 获取到最后一个节点
            if (parent.getData() >= data) {
                parent.setLeft(insertNode);
            } else {
                parent.setRight(insertNode);
            }
            //节点旋转保存红黑树平衡
            insertFix(parent);
        }
        return insertNode;
    }

    /**
     * 插入数据时进行数据节点的修复
     *
     * @param node
     */
    private void insertFix(RedBlackTreeNode node) {
        //根据父级节点是否存在并且是否是红色进行循环
        while (node.getParent() != null && isRed(node)) {
            RedBlackTreeNode parent = node.getParent();
            RedBlackTreeNode grandFather = parent.getParent();
            if (grandFather.getLeft() == parent) {
                //父父级节点左边是父节点
                RedBlackTreeNode uncle = grandFather.getRight();
                if (uncle != null && isRed(uncle)) {
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(grandFather);
                    node = grandFather;
                    continue;
                }

                if (parent.getRight() == node) {
                    //左旋
                }
                setBlack(parent);
                setRed(grandFather);
                //右旋

            } else {
                //右边节点是父级
            }
        }
    }

    /**
     * 判断是否是红色节点
     */
    public static boolean isRed(RedBlackTreeNode node) {
        return node != null && (node.isColor() == RedBlackTreeNode.RED);
    }

    /**
     * 判断是否是黑色节点
     */
    public static boolean isBlack(RedBlackTreeNode node) {
        return node == null || (node.isColor() == RedBlackTreeNode.BLACK);
    }

    /**
     * 设置节点颜色
     *
     * @param node
     */
    public static void setBlack(RedBlackTreeNode node) {
        if (node == null) {
            return;
        }
        node.setColor(RedBlackTreeNode.BLACK);
    }

    /**
     * 设置节点颜色
     *
     * @param node
     */
    public static void setRed(RedBlackTreeNode node) {
        if (node == null) {
            return;
        }
        node.setColor(RedBlackTreeNode.RED);
    }

}
